package com.cwj.lab4.SORT;

/**
 * 插入排序
 */
public class insertSort<T extends Comparable<T>> implements Sorted<T> {
    public void Sort(T[] nums) {
        insertSort.Sort(nums, 1);
    }

    //按增量的插入排序，主要是为了希尔排序准备
    public static <T extends Comparable<T>> void Sort(T[] nums, int k) {
        for (int i = 1; i < nums.length; i += k) {
            int j = 0;
            T tt = nums[i];
            for (j = i - k; j >= 0; j -= k) {
                if (tt.compareTo(nums[j]) < 0) {
                    nums[j + k] = nums[j];
                } else {
                    break;
                }
            }
            nums[j + k] = tt;
        }
    }
}